package greedy;

/**
 * 45. 跳跃游戏 II
 * <p>
 * 给你一个非负整数数组nums ，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * <p>
 * 假设你总是可以到达数组的最后一个位置。
 */
public class N45_JumpGameII {
    public int jump_v2(int[] nums) {
        int cur = 0, next = 0, step = 0;
        for (int i = 0; i < nums.length - 1; i++) { // 这里是nums数组的前length - 1个
            next = Math.max(next, nums[i] + i);
            if (i == cur) { // 到达当前最大范围
                step++;     // 因为遍历的只有前length - 1个，所以没到达终点
                cur = next;
            }
        }
        return step;
    }

    public int jump(int[] nums) {
        if (nums.length == 1) return 0;
        int cur = 0, next = 0, step = 0;
        for (int i = 0; i < nums.length; i++) {
            next = Math.max(nums[i] + i, next); // 下一步最大覆盖范围
            if (i == cur) { // i走到当前步的末尾
                if (cur != nums.length - 1) { // 当前最大覆盖范围不到数组最后一位
                    step++;
                    cur = next;
                    if (cur >= nums.length - 1) break; // 更新当前步之后的最大覆盖距离是否覆盖了数组最后一位
                } else break; // 走到末尾
            }
        }
        return step;
    }

    public static void main(String[] args) {
        N45_JumpGameII solution = new N45_JumpGameII();
        int[] nums = {2, 3, 3, 1, 5, 6, 7, 1, 1, 1, 1, 1, 1};
        System.out.println(solution.jump(nums));
    }
}
